package com.linkedlist;



import java.util.Stack;

/**
 * @author 江岸
 * @version V1.0
 * @ClassName: SingleLinkedList
 * @description: 单链表
 * @date 2020/9/2820:33
 * @since V1.0
 */
public class SingleLinkedList {
    public static void main(String[] args) {
        MyLinkedList myLinkedList = new MyLinkedList();
        myLinkedList.addByOrder(new HeroNode(1, "宋江", "及时雨"));
        myLinkedList.addByOrder(new HeroNode(3, "公孙胜", "入云龙"));
        myLinkedList.addByOrder(new HeroNode(6, "卢俊义", "玉麒麟"));
        myLinkedList.addByOrder(new HeroNode(88, "吴用", "智多星"));
        myLinkedList.addByOrder(new HeroNode(13, "卢俊义", "玉麒麟"));
        myLinkedList.addByOrder(new HeroNode(7, "吴用", "智多星"));
        //myLinkedList.show();
        System.out.println("-----------------------------------------------");
        //反转单链表
//        reversal(myLinkedList);
//        myLinkedList.show();
//        print(myLinkedList);
        //顺序合并两个链表
        MyLinkedList myLinkedList1 = new MyLinkedList();
        myLinkedList1.addByOrder(new HeroNode(2, "宋江", "及时雨"));
        myLinkedList1.addByOrder(new HeroNode(5, "公孙胜", "入云龙"));
        myLinkedList1.addByOrder(new HeroNode(7, "卢俊义", "玉麒麟"));
        myLinkedList1.addByOrder(new HeroNode(12, "吴用", "智多星"));
        myLinkedList1.addByOrder(new HeroNode(4, "宋江", "及时雨"));
        myLinkedList1.addByOrder(new HeroNode(14, "公孙胜", "入云龙"));
        myLinkedList1.addByOrder(new HeroNode(22, "卢俊义", "玉麒麟"));
        myLinkedList1.addByOrder(new HeroNode(8, "吴用", "智多星"));
        MyLinkedList merge = merge(myLinkedList, myLinkedList1);
        merge.show();
    }

    //反转单链表
    public static MyLinkedList reversal(MyLinkedList list) {
        HeroNode head = list.getHead();
        if (head.next == null) {
            return null;
        }
        HeroNode newHead = new HeroNode();
        HeroNode temp = head.next;
        while (true) {
            if (temp == null) {
                break;
            }
            HeroNode other = temp.next;
            temp.next = newHead.next;
            newHead.next = temp;
            temp = other;
        }
        head.next = newHead.next;
        newHead.next = null;
        return list;
    }

    //逆序打印单链表。栈
    public static void print(MyLinkedList list) {
        Stack<HeroNode> stack = new Stack<>();
        HeroNode head = list.getHead();
        if (head.next == null) {
            System.out.println("链表中无元素");
            return;
        }
        HeroNode temp = head.next;
        while (true) {
            if (temp == null) {
                break;
            }
            stack.push(temp);
            temp = temp.next;
        }
        while (stack.size() > 0) {
            System.out.println(stack.pop());
        }
    }

    //顺序合并两个有序单链表
    public static MyLinkedList merge(MyLinkedList a,MyLinkedList b){
        MyLinkedList list = new MyLinkedList();
        HeroNode headA = a.getHead();
        HeroNode headB = b.getHead();
        HeroNode head = list.getHead();
        if (headA.next==null && headB.next==null){
            return null;
        }
        HeroNode Atemp = headA.next;
        HeroNode Btemp = headB.next;
        HeroNode heroNode = head;
        while(true){
//            if (Atemp==null & Btemp==null){
//                break;
//            }
            if (Atemp == null){
//                HeroNode Bother =  Btemp.next;
//                Btemp.next = null;
//                heroNode.next = Btemp;
//                Btemp = Bother;
                heroNode.next = Btemp;
                break;
            }else if(Btemp == null){
//                HeroNode Aother =  Atemp.next;
//                Atemp.next = null;
//                heroNode.next = Atemp;
//                Atemp = Aother;
                heroNode.next = Atemp;
                break;
            }else {
                if (Atemp.no<=Btemp.no){
                    HeroNode Aother =  Atemp.next;
                    Atemp.next = null;
                    heroNode.next = Atemp;
                    Atemp = Aother;
                }else {
                    HeroNode Bother =  Btemp.next;
                    Btemp.next = null;
                    heroNode.next = Btemp;
                    Btemp = Bother;
                }
            }
            heroNode = heroNode.next;
        }
        return list;
    }

}

//定义一个heroNode，每个HeroNode对象就是一个节点
class HeroNode {
    public int no;
    public String name;
    public String nickName;
    public HeroNode next;//指向下一个节点

    public HeroNode(int no, String name, String nickName) {
        this.no = no;
        this.name = name;
        this.nickName = nickName;
    }

    public HeroNode() {
    }

    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickName='" + nickName + '\'' +
                '}';
    }
}

//定义一个单链表
class MyLinkedList {
    //初始化一个头节点，头节点不要动，不存放具体的数据
    private HeroNode head = new HeroNode(0, "", "");

    public HeroNode getHead() {
        return this.head;
    }

    //普通增加，找到最后节点，改一下next的指向即可
    public void add(HeroNode heroNode) {
        //因为head不能动，因此需要一个辅助变量temp
        HeroNode temp = head;
        //遍历链表，找到最后
        while (true) {
            if (temp.next == null) {
                break;
            }
            //如果没有找到最后，则将temp后移
            temp = temp.next;
        }
        temp.next = heroNode;
    }

    //第二种添加方法，根据排名添加到指定位置(如果排名存在，则提示添加失败)
    public void addByOrder(HeroNode heroNode) {
        HeroNode temp = head;
        boolean flag = false;//表示添加的编号是否存在，默认为false
        while (true) {
            if (temp.next == null) {
                break;
            }
            if (temp.next.no > heroNode.no) {
                //找到地方，就在该temp后面插入
                break;
            } else if (temp.next.no == heroNode.no) {
                //编号已存在
                flag = true;
                break;
            }
            temp = temp.next;//后移即遍历
        }
        //判断flag
        if (flag) {
            System.out.printf("准备插入的英雄编号%d已经存在", heroNode.no);
        } else {
            //插入
            heroNode.next = temp.next;
            temp.next = heroNode;
        }


    }

    //修改
    public void update(HeroNode heroNode) {
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }
        HeroNode temp = head.next;
        boolean flag = false;
        while (true) {
            if (temp == null) {
                break;
            }
            if (temp.no == heroNode.no) {
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag) {
            temp.name = heroNode.name;
            temp.nickName = heroNode.nickName;
        } else {
            System.out.println("没有这个编号的英雄");
        }
    }

    //删除
    public void delete(int no) {
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }
        HeroNode temp = head;
        boolean flag = false;
        while (true) {
            if (temp.next == null) {
                break;
            }
            if (temp.next.no == no) {
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag) {
            HeroNode h;
            h = temp.next;
            temp.next = temp.next.next;
            h.next = null;
        } else {
            System.out.println("没有这个编号的英雄");
        }

    }

    //遍历
    public void show() {
        HeroNode temp = head;
        while (true) {
            if (temp.next == null) {
                break;
            }
            temp = temp.next;
            System.out.println(temp);
        }
    }
}
